POJ2505 A multiplication game

题解：

博弈论题不打个sg函数的表怎么行呢？

于是给出一个打表程序：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    char c=getchar();bool f=0;x=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0) putchar('-'),write(-x);
    else{if(x>9) write(x/10);putchar('0'+x%10);}
}

#define int long long

const int N=1005;
int sg[N];
bool s[N];

signed main(){
    for(int i=2;i<=1000;i++){
        memset(s,0,sizeof s);
        for(int j=2;j<=9;j++){
            int nxt=i/j;
            if(i%j) nxt++;
            s[sg[nxt]]=1;
        }
        for(int j=0;;j++) if(!s[j]){
            sg[i]=j;
            break;
        }
    }
    for(int i=1;i<=1000;i++) if(!sg[i]) printf("#%lld:%lld\n",i,sg[i]);
}

下面是必败的情况（中间省略）：

有理有据大眼观察进行分析

为什么会在18那断掉，然后又在163那回来呢？

打开计算器，发现163/18=9.0555…，162/18=9，324=18*18

再加上小于10的数都是必胜的，我们容易总结出若一个数不断除以18，最后结果小于10，那它就是必胜的，否则必败

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

#define int long long

int n;

signed main(){
    while(scanf("%lld",&n)==1){
        while(n>18) n=(n-1)/18+1;
        if(n<=9) puts("Stan wins.");
        else puts("Ollie wins.");
    }
}